package com.leetcode.nc02;

import com.leetcode.entity.ListNode;

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return;

        ListNode slow = head;
        ListNode fast = head.next;
        // 寻找中间节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        ListNode newHead = reverse(mid);


        while (newHead != null) {
            ListNode temp = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = temp;
        }
    }

    //反转链表
    public ListNode reverse(ListNode head) {
        if (head == null)
            return head;
        ListNode tail = head;
        head = head.next;
        tail.next = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = tail;
            tail = head;
            head = tmp;
        }
        return tail;
    }
}

